//
// Created by ASUS on 2024/12/12/星期四.
//
#include <iostream>
#include <vector>

using namespace std;

class BIT2D {
private:
	vector<vector<int>> bit;
	int n, m;

	inline int lowbit(int x) {
		return x & (-x);
	}

public:
	BIT2D(int n, int m) : n(n), m(m) {
		bit.assign(n + 1, vector<int>(m + 1, 0));
	}

	void update(int x, int y, int val) {
		for (int i = x; i <= n; i += lowbit(i)) {
			for (int j = y; j <= m; j += lowbit(j)) {
				bit[i][j] += val;
			}
		}
	}

	int query(int x, int y) {
		int sum = 0;
		for (int i = x; i > 0; i -= lowbit(i)) {
			for (int j = y; j > 0; j -= lowbit(j)) {
				sum += bit[i][j];
			}
		}
		return sum;
	}

	int queryRegion(int x1, int y1, int x2, int y2) {
		return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
	}
};